#pragma once
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <queue>
#include <climits>
#include <stdexcept>
#include <functional>
#include <algorithm>
#include "../并查集源码/UnionFindSet.h"

using namespace std;
//邻接矩阵
namespace matrix
{
    //顶点     边权值      不相连的默认值       是否是有向图默认为假
    template <class V, class W, W MAX_W = INT_MAX, bool Direction = false>
    class graph
    {
    private:
        vector<V> vertexs; //顶点集合
        map<V, size_t> indexmap;
        vector<vector<W>> matrix;                         //储存边的矩阵
        typedef class graph<V, W, MAX_W, Direction> self; //图的别名
    public:
        graph() = default; //构建默认 构造函数
        graph(const V *_vertexs, size_t n)
        {
            vertexs.reserve(n);
            for (int i = 0; i < n; i++)
            {
                vertexs.push_back(_vertexs[i]);
                indexmap[_vertexs[i]] = i;
            }

            matrix.resize(n);
            for (int i = 0; i < n; i++)
            {
                matrix[i].resize(n, MAX_W);
            }
        }

        size_t GetVertexIndex(const V &src)
        {
            // typename std:: map<V,size_t>::iterator ret = indexmap.find(src);
            auto ret = indexmap.find(src);
            if (ret != indexmap.end())
            {
                return ret->second;
            }
            else
            {
                //不存在时报异常
                throw invalid_argument("不存在的顶点");
                return -1; //在编译时编译器会检查是否有返回
            }
        }
        void _AddEdge(const size_t &srci, const size_t &dsti, const W &w)
        {
            matrix[srci][dsti] = w;
            //是否是无向图
            if (Direction == false)
            {
                matrix[dsti][srci] = w;
            }
        }
        //添加边权值
        void AddEdge(const V &src, const V &dst, const W &w)
        {
            size_t srci = GetVertexIndex(src);
            size_t dsti = GetVertexIndex(dst);

            _AddEdge(srci, dsti, w);
        }
        void Print()
        {
            // 打印顶点和下标映射关系
            for (size_t i = 0; i < vertexs.size(); ++i)
            {
                cout << vertexs[i] << "-" << i << " ";
            }
            cout << endl
                 << endl;

            cout << "  ";
            for (size_t i = 0; i < vertexs.size(); ++i)
            {
                cout << i << " ";
            }
            cout << endl;

            // 打印矩阵
            for (size_t i = 0; i < matrix.size(); ++i)
            {
                cout << i << " ";
                for (size_t j = 0; j < matrix[i].size(); ++j)
                {
                    if (matrix[i][j] != MAX_W)
                        cout << matrix[i][j] << " ";
                    else
                        cout << "#"
                             << " ";
                }
                cout << endl;
            }
            cout << endl
                 << endl;

            // 打印所有的边
            for (size_t i = 0; i < matrix.size(); ++i)
            {
                for (size_t j = 0; j < matrix[i].size(); ++j)
                {
                    if (i < j && matrix[i][j] != MAX_W)
                    {
                        cout << vertexs[i] << "-" << vertexs[j] << ":" << matrix[i][j] << endl;
                    }
                }
            }
        }

        //广度优先遍历
        void BFS(const V &src)
        {
            size_t srci = GetVertexIndex(src);

            //层序遍历的遍历顺序队列 入队标记容器
            queue<size_t> q;
            vector<bool> visited(vertexs.size(), false);

            q.push(srci);
            visited[srci] = true;

            size_t n = q.size();
            while (!q.empty())
            {
                //遍历同一层的
                while (n--)
                {
                    int front = q.front();
                    q.pop();
                    cout << front << ':' << vertexs[front] << " ";
                    //添加有边但没有遍历的顶点
                    for (int i = 0; i < vertexs.size(); ++i)
                    {
                        if (matrix[front][i] != MAX_W && visited[i] == false)
                        {
                            q.push(i);
                            visited[i] = true;
                        }
                    }
                }
                cout << endl;
                n = q.size();
            }
            cout << endl;
        }
        void _DFS(size_t srci, vector<bool> &visited)
        {
            cout << srci << ":" << vertexs[srci] << endl;
            visited[srci] = true;
            //找相连但没有访问的顶点
            for (int i = 0; i < vertexs.size(); ++i)
            {
                if (matrix[srci][i] != MAX_W && visited[i] == false)
                {
                    _DFS(i, visited);
                }
            }
        }
        //深度优先遍历
        void DFS(const V &src)
        {
            size_t srci = GetVertexIndex(src);

            vector<bool> visited(vertexs.size(), false);

            _DFS(srci, visited);
            for (int i = 0; i < visited.size(); ++i)
            {
                if (visited[i] == false)
                {
                    _DFS(i, visited);
                }
            }
        }

        struct Edge
        {
            size_t srci;
            size_t dsti;
            W w;
            Edge(const size_t _srci, const size_t _dsti, const W &_w)
                : srci(_srci), dsti(_dsti), w(_w)
            {
            }
            bool operator>(const Edge &e) const
            {
                return w > e.w;
            }
        };

        //最小生成树 kruskal 算法
        W Kruskal(self &mintree)
        {
            size_t size = vertexs.size();
            //初始化最小生成树
            mintree.indexmap = indexmap;
            mintree.vertexs = vertexs;
            mintree.matrix.resize(size);
            for (int i = 0; i < size; ++i)
            {
                mintree.matrix[i].resize(size, MAX_W);
            }

            //使用边权值 生成小堆 在构建最小生成树时就用贪心算法 构成边
            priority_queue<Edge, vector<Edge>, greater<Edge>> minque;
            for (int i = 0; i < size; ++i)
            {
                for (int j = 0; j < size; ++j)
                {
                    // i<j 只遍历一半邻接矩阵
                    if (i < j && matrix[i][j] != MAX_W)
                        minque.push(Edge(i, j, matrix[i][j]));
                }
            }

            //构建最小生成树
            dzp::UnionFindSet minset(size); //保存连接关系 防止 连环
            W totalw = W();                 //保存最小边权值
            size_t n = 0;                   //保存n-1条边

            while (!minque.empty())
            {
                Edge tmp = minque.top();
                minque.pop();
                if (!minset.InSet(tmp.srci, tmp.dsti))
                {
                    // cout << vertexs[tmp.srci] << "->" << vertexs[tmp.dsti] <<":"<<tmp.w << endl;
                    mintree._AddEdge(tmp.srci, tmp.dsti, tmp.w);
                    minset.Union(tmp.srci, tmp.dsti);
                    ++n;
                    totalw += tmp.w;
                }
                else
                {
                    // cout << "构成环：";
                    // cout << vertexs[tmp.srci] << "->" << vertexs[tmp.dsti] << ":" << tmp.w << endl;
                }
            }

            if (n != (size - 1))
            {
                return W();
            }
            return totalw;
        }

        W Prim(self &mintree, const V &src)
        {
            size_t size = vertexs.size();
            //初始化最小生成树
            mintree.indexmap = indexmap;
            mintree.vertexs = vertexs;
            mintree.matrix.resize(size);
            for (int i = 0; i < size; ++i)
            {
                mintree.matrix[i].resize(size, MAX_W);
            }

            //保存并遍历最小边
            priority_queue<Edge, vector<Edge>, greater<Edge>> minque;
            //以连接的顶点
            vector<bool> X(size, false);
            vector<bool> Y(size, true);
            size_t srci = GetVertexIndex(src);
            X[srci] = true;
            Y[srci] = false;

            //把顶点的所有边都遍历添加
            for (int i = 0; i < size; ++i)
            {
                if (matrix[srci][i] != MAX_W)
                {
                    minque.push(Edge(srci, i, matrix[srci][i]));
                }
            }

            //找出最小的边
            size_t n = 0;
            W totalw = W();
            while (!minque.empty())
            {
                Edge tmp = minque.top();
                minque.pop();
                while (X[tmp.dsti])
                {
                    // cout << "构成环:";
                    // cout << vertexs[tmp.srci] << "->" << vertexs[tmp.dsti] << ":" << tmp.w << endl;
                    tmp = minque.top();
                    minque.pop();
                }

                mintree._AddEdge(tmp.srci, tmp.dsti, tmp.w);
                // cout << vertexs[tmp.srci] << "->" << vertexs[tmp.dsti] << ":" << tmp.w << endl;
                X[tmp.dsti] = true;
                Y[tmp.dsti] = false;
                totalw += tmp.w;
                ++n;
                if (n == size - 1)
                    return totalw;

                for (int i = 0; i < size; ++i)
                {
                    if (matrix[tmp.dsti][i] != MAX_W && Y[i])
                    {
                        minque.push(Edge(tmp.dsti, i, matrix[tmp.dsti][i]));
                    }
                }
            }
            if (n != (size - 1))
            {
                return W();
            }
            return totalw;
        }

        //单源最短路径
        void Dijkstra(const V &src, vector<W> &dist, vector<int> &pPath)
        {
            size_t size = vertexs.size();
            dist.resize(size, MAX_W);
            pPath.resize(size, -1);

            size_t srci = GetVertexIndex(src);
            vector<bool> Yes(size, false); //保存已知的顶点

            dist[srci] = 0;     //起点的路径值为0
            pPath[srci] = srci; //起点的上级路径

            //找路径
            for (int i = 0; i < size; i++)
            {
                //在没有确定的顶点集合中找最小路径顶点
                size_t u = 0;
                int min = MAX_W; //
                for (int j = 0; j < size; j++)
                {
                    if ((!Yes[j]) && dist[j] < min)
                    {
                        min = dist[j];
                        u = j;
                    }
                }
                Yes[u] = true;
                //更新为确定集合的最短路径
                for (int j = 0; j < size; ++j)
                {
                    //把和u连接的顶点的路径值 都更新成 从起点到该顶点的最短路径
                    if (Yes[j] == false && matrix[u][j] != MAX_W && (matrix[u][j] + dist[u]) < dist[j])
                    {
                        dist[j] = matrix[u][j] + dist[u];
                        pPath[j] = u;
                    }
                }
            }
        }

        //最短路径的打印
        void PrintShortPath(const V &src, const vector<W> &dist, const vector<int> &pPath)
        {
            size_t srci = GetVertexIndex(src);
            size_t size = vertexs.size();
            for (int i = 0; i < size; ++i)
            {
                vector<int> path;
                size_t p = i;
                if (i == srci)
                    continue;

                while (p != srci)
                {
                    path.push_back(p);
                    p = pPath[p];
                }
                path.push_back(srci);
                reverse(path.begin(), path.end());

                for (auto &e : path)
                {
                    cout << vertexs[e] << "->";
                }
                cout << dist[i] << endl;
            }
        }

        //最短路径带负权值
        bool BellmanFord(const V &src, vector<W> &dist, vector<int> &pPath)
        {
            size_t size = vertexs.size();
            dist.resize(size, MAX_W);
            pPath.resize(size, -1);

            size_t srci = GetVertexIndex(src);
            dist[srci] = W();
            pPath[srci] = srci;

            //看是否会对前面的更新 有影响 ，有就要再次更新
            for (int k = 0; k < size; k++)
            {
                bool update = false;
                //遍历更新所有的边从起点的最短路径值
                for (int i = 0; i < size; ++i)
                {
                    for (int j = 0; j < size; ++j)
                    {
                        //把i 所有连接的顶点 j都进行比较  s->i dist[i] + i->j 是否小于 s->j 的
                        if (matrix[i][j] != MAX_W && dist[i] + matrix[i][j] < dist[j])
                        {
                            update = true;
                            dist[j] = dist[i] + matrix[i][j];
                            pPath[j] = i;
                        }
                    }
                }
                if (!update)
                    break;
            }
            // 还能更新就是带负权回路
            for (size_t i = 0; i < size; ++i)
            {
                for (size_t j = 0; j < size; ++j)
                {
                    // srci -> i + i ->j
                    if (matrix[i][j] != MAX_W && dist[i] + matrix[i][j] < dist[j])
                    {
                        return false;
                    }
                }
            }
            return true;
        }

        void FloydWarshall(vector<vector<W>> &vvDist, vector<vector<int>> &vvpPath)
        {
            size_t size = vertexs.size();
            vvDist.resize(size);
            vvpPath.resize(size);

            //把已有的图关系拷贝vvdist
            for (int i = 0; i < size; i++)
            {
                vvDist[i].resize(size, MAX_W);
                vvpPath[i].resize(size, -1);
                for (int j = 0; j < size; ++j)
                {
                    vvDist[i][j] = matrix[i][j];
                    vvpPath[i][j] = i;
                    if (i == j)
                    {
                        vvDist[i][j] = W();
                    }
                }
            }

            // i->j   的路径中的 i->K k->j  所有顶点都比较一边
            for (int k = 0; k < size; ++k)
            {
                for (int i = 0; i < size; i++)
                {
                    for (int j = 0; j < size; j++)
                    {
                        // i->K存在 K->j 存在
                        if (vvDist[i][k] != MAX_W && vvDist[k][j] != MAX_W && 
                            vvDist[i][k] + vvDist[k][j] < vvDist[i][j])        // i->k的路径+k->j的路径小于i->j的路径就更形
                        {
                            vvDist[i][j] = vvDist[i][k] + vvDist[k][j];
                            vvpPath[i][j] = vvpPath[k][j]; // i->j的路径是 从k->j来的所以i->J的上一级顶点在k->J中
                        }
                    }
                }

                // 打印权值和路径矩阵观察数据
                for (size_t i = 0; i < size; ++i)
                {
                    for (size_t j = 0; j < size; ++j)
                    {
                        if (vvDist[i][j] == MAX_W)
                        {
                            // cout << "*" << " ";
                            printf("%3c", '*');
                        }
                        else
                        {
                            // cout << vvDist[i][j] << " ";
                            printf("%3d", vvDist[i][j]);
                        }
                    }
                    cout << endl;
                }
                cout << endl;

                for (size_t i = 0; i < size; ++i)
                {
                    for (size_t j = 0; j < size; ++j)
                    {
                        // cout << vvParentPath[i][j] << " ";
                        printf("%3d", vvpPath[i][j]);
                    }
                    cout << endl;
                }
                cout << "=================================" << endl;
            }
        }

    }; // class end
} // namespace end

//图 用邻接表 表示
namespace link_table
{
    template <class W>
    struct Edge
    {
        int dsti; //目标的下标
        W w;      //边权值
        Edge<W> *next;
        Edge(int _dsti, const W &_w)
            : dsti(_dsti), w(_w), next(nullptr)
        {
        }
    };

    template <class V, class W, bool Direction = false>
    class graph
    {
        typedef struct Edge<W> Edge;

    private:
        vector<V> vertexs;       //顶点的集合
        map<V, size_t> indexmap; //顶点与下标的映射
        vector<Edge *> tables;   //邻接表
    public:
        graph(const V *_vertexs, size_t n)
        {
            vertexs.reserve(n);
            for (int i = 0; i < n; ++i)
            {
                vertexs.push_back(_vertexs[i]);
                indexmap[_vertexs[i]] = i;
            }
            tables.resize(n, nullptr);
        }

        size_t GetVertexsInxdex(const V &src)
        {
            auto it = indexmap.find(src);
            if (it != indexmap.end())
            {
                return it->second;
            }
            else
            {
                throw invalid_argument("顶点不存在");
                return -1;
            }
        }
        void AddEdge(const V &src, const V &dst, const W &w)
        {
            size_t srci = GetVertexsInxdex(src);
            size_t dsti = GetVertexsInxdex(dst);

            Edge *tmp = tables[srci];
            while (tmp)
            {
                if (tmp->dsti == dsti)
                {
                    // std::cout<<"关系已存在"<<endl;
                    return;
                }
                tmp = tmp->next;
            }

            tmp = new Edge(dsti, w);
            tmp->next = tables[srci];
            tables[srci] = tmp;

            if (Direction == false)
            {
                tmp = new Edge(srci, w);
                tmp->next = tables[dsti];
                tables[dsti] = tmp;
            }
        }
        void Print()
        {
            // 顶点
            for (size_t i = 0; i < vertexs.size(); ++i)
            {
                cout << "[" << i << "]"
                     << "->" << vertexs[i] << endl;
            }
            cout << endl;

            for (size_t i = 0; i < tables.size(); ++i)
            {
                cout << vertexs[i] << "[" << i << "]->";
                Edge *cur = tables[i];
                while (cur)
                {
                    cout << "[" << vertexs[cur->dsti] << ":" << cur->dsti << ":" << cur->w << "]->";
                    cur = cur->next;
                }
                cout << "nullptr" << endl;
            }
        }
    };
}
